package q928_minMalwareSpread;

import CommonClass.UF;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class Solution {
    /*
    并查题型：具体结合注释理解
     */
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        UF uf = new UF(n);
        // 利用一个数组来记录哪些节点初始时是未被感染的 如果被感染 就置1
        int[] clean = new int[n];
        for (int infect : initial) clean[infect] = 1;
        // 接下来用干净的节点构建一个并查集
        for (int i = 0; i < n; i++) {
            if (clean[i] == 1) continue;
            for (int j = i + 1; j < n; j++) {
                if (clean[j] == 0 && graph[i][j] == 1) uf.union(i, j);
            }
        }
        // map中的结构：病毒节点 -> 它所感染的 代表们 所形成的set 也就是一个病毒节点能够感染的簇
        Map<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>();
        // 这个数组将会记录不同簇的代表 会被几个病毒节点所感染
        // 因为题目只能完全移除一个节点 如果一个簇会被两个及以上的病毒节点感染 那么移除其中的节点是没有用的
        int[] count = new int[n];
        for (int infect : initial) {
            HashSet<Integer> set = new HashSet<Integer>();
            for (int i = 0; i < n; i++) {
                if (clean[i] == 0 && graph[i][infect] == 1) set.add(uf.find(i));
            }
            map.put(infect, set);
            // 能够感染的对应代表+1
            for (Integer present : set) {
                count[present]++;
            }
        }
        // 类似924的做法
        int ans = -1, ansSize = -1;
        for (int infect : initial) {
            // 首先定义一个temp用来记录当前病毒节点能够感染的最大数量
            int temp = 0;
            HashSet<Integer> set = map.get(infect);
            // 只有当一个代表节点其连接的病毒节点只有一个时 移除病毒节点才有意义 否则移除了还是会被另一个感染
            // 因此要考虑count[present] == 1 然后temp加uf中对应代表其所在簇的size 也就是移除该节点后能够减少感染节点的数量
            for (Integer present : set) {
                if (count[present] == 1) temp += uf.size[present];
            }
            // 只有temp更大或者同样大且node的index更小时 才更新两者
            if (temp > ansSize || temp == ansSize && infect < ans) {
                ans = infect;
                ansSize = temp;
            }
        }
        return ans;
    }
}
